package samples.java.algorithm.sort;

import java.util.ArrayList;

/**
 * 桶排序
 *
 * @author wang.yuchuan
 * @createdAt 2018/12/9
 */
public class BucketSort {

    public static void sort(int[] array) {
        if (array.length == 0) {
            return;
        }

        // 先用一遍循环, 找出最小值、最大值
        int minValue = array[0], maxValue = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < minValue) {
                minValue = array[i];
            }
            if (array[i] > maxValue) {
                maxValue = array[i];
            }
        }

        // 默认每个桶里元素的数量
        final int BUCKET_SIZE = 10;
        // 需要使用的桶的数量 = (最大值 - 最小值) / 桶容量数量
        int bucketCount = (int) Math.floor((maxValue - minValue) / BUCKET_SIZE) + 1;

        ArrayList<ArrayList> buckets = new ArrayList<ArrayList>(bucketCount);
        for (int i = 0; i < buckets.size(); i++) {
            buckets.set(i, new ArrayList<Integer>());
        }

        for (int i = 0; i < array.length; i++) {
            int bucketIndex = (int) Math.floor((array[i] - minValue) / BUCKET_SIZE);
            buckets.get(bucketIndex).add(array[i]);
        }

        for (int i = 0; i < buckets.size(); i++) {
            ArrayList arrayList = buckets.get(i);
        }

    }

    public static void main(String[] args) {
        int[] arr = {3, 44, 5, 67, 4, 23, 42, 56, 78, 91, 2, 7, 9, 12, 16};

        sort(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
